package DailyQuestions;

import java.util.HashSet;

//正数数组的最小不可组成和
public class Day29_2 {
    public static void main(String[] args) {
        int[] ary={2,3,9};
        System.out.println(getFirstUnFormedNum(ary));
    }
   public static int getFirstUnFormedNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        HashSet<Integer> set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0;i < arr.length;i++) {
            min = Math.min(min, arr[i]);
            max += arr[i];
        }
        process(arr,0,0,set);
        for (int num = min + 1; num <= max; num++) {
            if (! set.contains(num)) {
                return num;
            }
        }
        return max + 1;

    }

    public static void process(int[] arr, int i, int preSum, HashSet<Integer> set) {
        //决策结束，把决策累加的和加入set中
        if (i == arr.length) {
            set.add(preSum);
            return;
        }
        //不要当前元素
        process(arr,i+1,preSum,set);
        //要当前元素
        process(arr,i+1,preSum + arr[i],set);
    }
}
